Specialization of Functional Logic Programs Based on Needed Narrowing

摘要

Many functional logic languages are based on narrowing, a unification-basedgoal-solving mechanism which subsumes the reduction mechanism of functionallanguages and the resolution principle of logic languages. Needed narrowing isan optimal evaluation strategy which constitutes the basis of modern(narrowing-based) lazy functional logic languages. In this work, we present thefundamentals of partial evaluation in such languages. We provide correctnessresults for partial evaluation based on needed narrowing and show that the niceproperties of this strategy are essential for the specialization process. Inparticular, the structure of the original program is preserved by partialevaluation and, thus, the same evaluation strategy can be applied for theexecution of specialized programs. This is in contrast to other partialevaluation schemes for lazy functional logic programs which may change theprogram structure in a negative way. Recent proposals for the partialevaluation of declarative multi-paradigm programs use (some form of) needednarrowing to perform computations at partial evaluation time. Therefore, ourresults constitute the basis for the correctness of such partial evaluators.